package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-28 11:06
 * @description: Functions of this class is
 * 官方题解：
 * public String LCS(String str1, String str2) {
 *     int maxLenth = 0;//记录最长公共子串的长度
 *     //记录最长公共子串最后一个元素在字符串str1中的位置
 *     int maxLastIndex = 0;
 *     int[] dp = new int[str2.length() + 1];
 *     for (int i = 0; i < str1.length(); i++) {
 *         //注意这里是倒叙
 *         for (int j = str2.length() - 1; j >= 0; j--) {
 *             //递推公式，两个字符相等的情况
 *             if (str1.charAt(i) == str2.charAt(j)) {
 *                 dp[j + 1] = dp[j] + 1;
 *                 //如果遇到了更长的子串，要更新，记录最长子串的长度，
 *                 //以及最长子串最后一个元素的位置
 *                 if (dp[j + 1] > maxLenth) {
 *                     maxLenth = dp[j + 1];
 *                     maxLastIndex = i;
 *                 }
 *             } else {
 *                 //递推公式，两个字符不相等的情况
 *                 dp[j + 1] = 0;
 *             }
 *         }
 *     }
 *     //最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
 *     return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
 * }
 **/
public class NoNo动态规划牛客最长公共子串 {
    /**
     * 简单版：
     * public String LCS(String str1, String str2) {
     *     int maxLenth = 0;//记录最长公共子串的长度
     *     //记录最长公共子串最后一个元素在字符串str1中的位置
     *     int maxLastIndex = 0;
     *     int[][] dp = new int[str1.length() + 1][str2.length() + 1];
     *     for (int i = 0; i < str1.length(); i++) {
     *         for (int j = 0; j < str2.length(); j++) {
     *             //递推公式，两个字符相等的情况
     *             if (str1.charAt(i) == str2.charAt(j)) {
     *                 dp[i + 1][j + 1] = dp[i][j] + 1;
     *                 //如果遇到了更长的子串，要更新，记录最长子串的长度，
     *                 //以及最长子串最后一个元素的位置
     *                 if (dp[i + 1][j + 1] > maxLenth) {
     *                     maxLenth = dp[i + 1][j+1];
     *                     maxLastIndex = i;
     *                 }
     *             } else {
     *                 //递推公式，两个字符不相等的情况
     *                 dp[i + 1][j+1] = 0;
     *             }
     *         }
     *     }
     *     //最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
     *     return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
     * }
     */
}